package main

import (
	"fmt"
	"gopkg.in/fatih/set.v0"
)

/**
假设你办了个广播节目，要让全美50个州的听众都收听得到。为
此，你需要决定在哪些广播台播出。在每个广播台播出都需要支付费
用，因此你力图在尽可能少的广播台播出。现有广播台名单如下。
州		电台
KONE   	id,nv,ut
KTWO	wa,id,mt
KTHREE	or,nv,ca
KFOUR	nv,ut
KFIVE	ca,az
......
每个广播台都覆盖特定的区域，不同广播台的覆盖区域可能重叠。
如何找出覆盖全美50个州的最小广播台集合呢？听起来很容易，但其实非常难。具体方法如下。
(1) 列出每个可能的广播台集合，这被称为幂集（power set）。可能的子集有2²个。计算代价比较高

近似算法
贪婪算法可化解危机！使用下面的贪婪算法可得到非常接近的解。
(1) 选出这样一个广播台，即它覆盖了最多的未覆盖州。即便这个广播台覆盖了一些已覆盖
的州，也没有关系。
(2) 重复第一步，直到覆盖了所有的州。
 */
func main()  {
	m := make(map[string]set.Interface, 10)
	//电台对应的州
	KONE:= set.New(set.NonThreadSafe)
	KONE.Add("id","nv","ut")
	KTWO:= set.New(set.NonThreadSafe)
	KTWO.Add("wa","id","mt")
	KTHREE:= set.New(set.NonThreadSafe)
	KTHREE.Add("or","nv","ca")
	KFOUR:= set.New(set.NonThreadSafe)
	KFOUR.Add("nv","ut")
	KFIVE:= set.New(set.NonThreadSafe)
	KFIVE.Add("ca","az")
	m["KONE"] = KONE
	m["KTWO"] = KTWO
	m["KTHREE"] = KTHREE
	m["KFOUR"] = KFOUR
	m["KFIVE"] = KFIVE
	statesNeeded := set.New(set.NonThreadSafe)
	statesNeeded.Add("id","nv","ut","wa","or","ca","az","mt")
	statesFinalList := set.New(set.NonThreadSafe)
	for {
		bestStation := findBestStation(m,&statesNeeded)
		if bestStation==""{
			break
		}
		statesFinalList.Add(bestStation)
	}
	fmt.Println(statesFinalList)
}

func findBestStation(m map[string]set.Interface,statesNeeded *set.Interface) string {
	var bestStation string

	//本次循环能覆盖的最多的州
	coveredStates:=set.New(set.NonThreadSafe)
	for station,states := range m{

		//交集
		toBeCovered := set.Intersection(*statesNeeded,states)

		//比较之前能覆盖最多的州电台覆盖的州数量 和 当前能覆盖最多的州的数量
		if coveredStates.Size()<toBeCovered.Size(){

			//如果在剩余需要覆盖的州中，当前能覆盖的更多，则设置为最好的电台
			coveredStates = toBeCovered
			bestStation = station
		}
	}

	//没有获取到最好的州
	if coveredStates.IsEmpty(){
		return ""
	}
	//差集，把需要覆盖的州删掉该循环中最多的覆盖的州
	*statesNeeded = set.Difference(*statesNeeded,coveredStates)

	//map中删掉这个电台，防止重复遍历
	delete(m,bestStation)
	return bestStation
}
